class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) {
            return;
        }
        /* 1. 找顺序对(前小后大) */
        int idx = len - 2;
        while ((idx >= 0) && (nums[idx] >= nums[idx + 1])) {
            idx--;
        }

        if (idx == -1) {
            /* 整个数组是降序的，没有更大字典序排列 */
            reverse(nums.begin(), nums.end());
            return;
        }

        /* 2. 找到第一个升序对后，找比该元素大的最小元素位置 */
        int minGreaterPos = len - 1;
        while (minGreaterPos > idx && nums[minGreaterPos] <= nums[idx]) {
            minGreaterPos--;
        }
        swap(nums[idx], nums[minGreaterPos]);
        reverse(nums.begin() + idx + 1, nums.end());
        return;
    }
};